package java_1_24.stack_queue.queue.impl;

import java_1_24.stack_queue.queue.Queue;

import java.util.NoSuchElementException;

/**
 * 队列的实现
 * 基于链表实现的基础队列
 */
public class MyQueue<E> implements Queue<E> {
    //节点--用成员内部类-链表的每个节点
    private class Node{
        E val;
        Node next;
        public Node(E val) {
            this.val = val;
        }
    }
    //当前队列元素个数
    private int size;
    //链表队首
    private Node head;
    //队尾
    private Node tail;
    //入队-尾插
    @Override
    public void offer(E val) {
        Node node=new Node(val);
        if(head==null){
            //此时队列为空(头节点都为空尾也肯定为空)
            head=tail=node;
        }else{
            tail.next=node;
            tail=node;
        }
        size++;
    }
    //出队-头删-返回队首元素(未删除前的)
    @Override
    public E poll() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot pull!");
        }else{
            E val=head.val;
            Node node=head;
            head=head.next;
            node.next=null;//原先头节点脱钩
            size--;
            return val;
        }
    }

    @Override
    public E peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }else{
            return head.val;
        }
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append("front [");
        //链表遍历
        for (Node x = head; x!=null; x=x.next) {
            sb.append(x.val);
            if(x.next!=null){
                //未走到链表尾部
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
